package Hot100;

import java.util.HashMap;
import java.util.LinkedHashSet;

/**
 * @author zhangmin
 * @create 2021-12-30 10:38
 *
 * 460. LFU 缓存
 * 请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。
 * 需要记录使用频率，存储key-freq的映射用于操作freq的变化，存储freq-key的映射用于找到freq的最小，用minfreq记录最小的freq是多少，可以直接访问到
 * 还需要记录访问时间顺序，freq-key的映射应该是一对多的，所以，里面的key部分需要用LinkedHashSet，按时间顺序存储key的列表
 * 还有能随用随取，用map存储
 */
public class LFUCache {

    int capacity;
    int minFreq;
    //map记录所以的键值对
    HashMap<Integer,Integer> map;
    //keyToFreq记录从key到Freq的映射
    HashMap<Integer,Integer> keyToFreq;
    //freqToKey记录从freq到key的映射
    HashMap<Integer, LinkedHashSet<Integer>> freqToKey;

    // 用数据结构的容量 capacity 初始化对象
    public LFUCache(int capacity) {
        this.capacity=capacity;
        this.minFreq=0;
        map=new HashMap<>();
        keyToFreq=new HashMap<>();
        freqToKey=new HashMap<>();
    }

    //如果键 key 存在于缓存中，则获取键的值，否则返回 -1 。
    public int get(int key) {
        //先判断key是否在map中，不存在就直接返回-1
        if (!map.containsKey(key)) return -1;
        //需要将key的访问频率+1，并更新从freq到key的映射，从原本的链表中删除，插入到freq+1的链表中
        addFreq(key);
        return map.get(key);
    }

    //如果键 key 已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量 capacity 时，则应该在插入新项之前，移除最不经常使用的项。
    //在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近最久未使用 的键。
    public void put(int key, int value) {
        if (this.capacity<=0) return;
        //插入元素时，首先判断容量是否够用，够用时直接插入即可，不够时需要先删除最小频率的元素，然后再插入
        if (map.containsKey(key)){
            map.put(key,value);
            addFreq(key);
            return;
        }
        if (this.capacity<=map.size()){
            removeMinFreq();
        }
        //插入map
        map.put(key,value);
        //插入KF表
        keyToFreq.put(key,1);
        //插入FK
        freqToKey.putIfAbsent(1,new LinkedHashSet<>());
        freqToKey.get(1).add(key);
        this.minFreq=1;
    }
    public void addFreq(int key){
        Integer freq = keyToFreq.get(key);
        //更新kf表
        keyToFreq.put(key,freq+1);
        //更新fk表
        freqToKey.get(freq).remove(key);   //在freq的队列中删除key
        freqToKey.putIfAbsent(freq+1,new LinkedHashSet<>());   //在freq+1的队列中添加key
        freqToKey.get(freq+1).add(key);
        if (freqToKey.get(freq).isEmpty()){
            //freq对应的链表空了，需要删除freq
            freqToKey.remove(freq);
            //如果这个freq刚好是minfreq则需要更新
            if (freq==minFreq){
                //当前的freq访问后一定会加入到freq+1中，所以最小的频率一定是++
                this.minFreq++;
            }
        }
    }

    //删除最小的频率的元素，当容量不够时调用
    public void removeMinFreq(){
        //找到频率最小的key的list
        LinkedHashSet<Integer> minKeyList = freqToKey.get(minFreq);
        //找到队列中第一个元素，就是需要删除的key
        Integer deletedkey = minKeyList.iterator().next();
        //更新FK，在FreqToKey中删除key
        minKeyList.remove(deletedkey);
        if (minKeyList.isEmpty()){
            //最小freq的list空了，删除这个freq---不需要更新minFreq的值,因为删除最小值一定是在容量超出的情况下，下一步是添加元素，刚添加的元素一定是freq=1会更新miFreq
            freqToKey.remove(this.minFreq);
        }
        //更新KF
        keyToFreq.remove(deletedkey);
        //更新map
        map.remove(deletedkey);
    }
}
